///////////////////////////////////////////////////////////////////////////////
// 该文件建立了C++中二叉树数据结构的基础代码，包括节点、插入节点、构建完整示例链表，删除这个链
// 表等. 
//
// 
//                                                       Author: Xian Yang
//                                                     Date Time: 2023.11.26
///////////////////////////////////////////////////////////////////////////////

#pragma once

#include <bits/stdc++.h>
#include <queue>
#include <memory>

struct BTreeNode {
public:
    BTreeNode() : val(0), left(nullptr), right(nullptr) {}

    BTreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}

    BTreeNode(int _val, BTreeNode* _left, BTreeNode* _right) 
            :  val(_val), left(_left), right(_right) {}
public:
    int val;
    BTreeNode *left;   // left  hand child
    BTreeNode *right;  // right hand child
};

// 往当前已经存在的二叉树中插入一个节点
// TODO: 注意这里的root是指针的引用
// void insert(BTreeNode*& root, int value) {
//     if (root == nullptr) {
//         root = new BTreeNode(value);
//     } else {
//         if (value < root->val) {
//             insert(root->left, value);
//         } else {
//             insert(root->right, value);
//         }
//     }
//     return;
// }

// // 使用指定的值向量, 创建一颗二叉搜索树
// void buildBSTree(BTreeNode* root) {
//     if (root != nullptr)  return;
//     std::vector<int> vals = {5, 3, 8, 1, 4, 7, 9};

//     for (auto val : vals) {
//         insert(root, val);
//     }
//     return;
// }

// // 释放二叉搜索树内存
// void deleteTree(BTreeNode* root) {
//     if (root == nullptr) return;
//     deleteTree(root->left);
//     deleteTree(root->right);
//     delete root;
//     root = nullptr;
// }
